The Rijndael block cipher is a symmetric cryptographic algorithm, based on the use of simple byte operations, that was designed as a candidate for the Advanced Encryption Standard (AES). The National Institute of Standards and Technology (NIST) approved a Rijndael standard as the AES, as specified in the Federal Information Processing Standard (FIPS), FIPS-197. This standard specifies a symmetric encryption algorithm (hereinafter referred to as “the AES algorithm”) that may be used to protect electronic data.
In the following description, the use of the terms transformation, bit, block, byte, cipher key, key expansion, round key, state, and word, is as defined in the AES algorithm standard, FIPS-197.
The AES algorithm can be used to encrypt/decrypt information utilizing cryptographic keys of 128, 192, or 256 bits and data blocks of 128 bits. In general, the encryption includes processing of an input data block a predetermined number of
rounds. The number of rounds required is determined according to the size of key length used.
FIG. 1A is a flow chart illustrating the AES ciphering process of a data block D (plaintext) with a ciphering key K, which are being loaded in step 100. The number of rounds N is determined according to the key length (e.g., for a 128 bits key, N=10). The process begins with the so-called Add Round Key transformation 101, in which the state D is set to equal the addition of the ciphering key K=K0 and the input data block (D). Rounds 1 to N−1 (steps 101, 102, and 105) are performed as long as the condition set in step 102 is not fulfilled.
Each round begins in Add Round Key transformation 101 of the state D which is performed with a corresponding Round Key Ki (i=1, 2, . . . , N−1). The Add Round Key transformation is followed by a sequence of transformations 105 which are applied to the state D, and which are not of particular interest in this invention, and thus are not discussed herein in detail for the sake of brevity.
If the condition in step 102 is satisfied, an additional set of transformations 106 of the state D are performed, followed by another Add Round Key transformation 109, in which the last Round Key KN is used. The process is then terminated by outputting the Block Cipher obtained in the state D′ (ciphertext). As will be explained hereinafter, each Round Key is recursively computed utilizing the value of the previous key, i.e., Ki=f(Ki−1). This computation (not shown in FIG. 1A) is also known as the key expansion process.
Similarly, during the decryption, as shown in the flow chart in FIG. 1B, the same number of rounds is used in the deciphering process utilizing the inverse transformations. A Cipher Block (D′) (ciphertext) and the last Round Key KN that was used in the ciphering, are input in step 110. The first transformation in step 111 is an Add Round Key, in which the state D′ is set according to the value of the last Round Key KN. The decryption, also termed herein as the inverse cipher, comprises a sequence of inverse transformations 111, and 115. The respective Add Round Key transformation performed in step 111 in each round uses an inverse key expansion process to derive the corresponding Round Key Ki−1=f−1(Ki) (i=9, 8, . . . 2).
Once the condition in step 112 is satisfied, the inverse transformations of the state 116 are performed, and in step 114, the final Add Round Key transformation is carried out to recover the plaintext D, by utilizing the first Round Key K0.
As shown in FIGS. 1A and 1B, the AES algorithm requires a consecutive process of recursive key expansion processes to take place for a proper block ciphering and deciphering. While in the block ciphering the process is initiated with the original secret key K and proceeds “forward” utilizing new keys obtained via the key expansion process, during the block deciphering the key expansion is performed “backwards”. Namely, the first key used for block deciphering is the one that was obtained in the last key expansion of the block ciphering process KN, and each successive Round Key is then obtained by an inverse key expansion process which recovers the previous Round Keys of the block ciphering process.
This key scheduling imposes several restrictions on AES implementations, particularly on hardware implementations. The recursive nature of the key scheduling requires a number of key expansions in order to obtain a specific Round Key. One common solution is to store the Round Keys in a memory device (AES/Rijndael Core, SecuCore 2001) and for each cipher/decipher round, fetching the corresponding Round Key from the memory device. This solution enables managing the key scheduling conveniently, but it is, however, considered costly in hardware terms and processing time due to the silicon area needed for a memory device which should be provided in addition to a key expansion unit e.g., for 128-bits key a memory space of 128×11=1408 bits of memory are required, and due to CPU time required to fetch the stored keys.
Another possible way to address the key scheduling problem is to provide a key expansion module for the block ciphering process, and an inverse key expansion module to be used in the block deciphering process (“Implementation of the block cipher Rijndael using Altera FPGA”, P. Mroczkowski). Although in such implementations, a memory device for storing only a single key is required (e.g., 128 bits of memory in order to produce the next/previous key) such implementations are still expensive due to the use of two different modules for key scheduling (gate count and die area), particularly in view of the great resemblance between the key expansion process, and its inverse implementation, which will be discussed in detail hereinafter.
All the methods described above have not yet provided satisfactory solutions to the problems involved in hardware implementations of Rijndael block ciphering/deciphering key scheduling.
Accordingly, there exists a need for a key scheduler capable of performing key expansion for the block ciphering and deciphering processes and/or a key scheduler implementation with a minimal gate count.